#include <iostream>
#include <vector>
using namespace std;

vector<int> merge2(vector<int> &a, vector<int> &b){
    int m = a.size(), n = b.size();
    vector<int> c;
    int i = 0, j = 0;
    while (i < m && j < n)
    {
        // 如果a小于，就放入a，如果b小就放入b
        if (a[i] < b[j])
        {
            c.push_back(a[i]);
            i++;
        }else{
            c.push_back(b[j]);
            j++;
        }
        
    }
    while (i < m)
    {
        // 归并a
        c.push_back(a[i]);
        i++;
    }
    while (j < n)
    {
        // 归并b
        c.push_back(b[j]);
        j++;
    }
    return c;
}

vector<int> intersect(vector<int> &a, vector<int> &b){
    int m = a.size(), n = b.size();
    vector<int> c;
    int i = 0, j = 0;
    while (i < m && j < n)
    {
        if (a[i] < b[j])
        {
            i++;
        }else if (a[i] > b[j])
        {
            j++;
        }else{
            c.push_back(a[i]);
            i++, j++;
        }
    }
    return c;
    
}


int main(){
    vector<int> a;
    vector<int> b;
    for (int i = 0; i < 10; i++)
    {
        a.push_back(i);
        b.push_back(i * 10 + 1 - 6);
    }
    vector<int> res = merge2(a, b);
    vector<int> res2 = intersect(a, b);

    for (vector<int>::iterator it = res.begin(); it < res.end(); it++)
    {
        cout << *it << endl;
    }

    for (vector<int>::iterator it = res2.begin(); it < res2.end(); it++)
    {
        cout << "二路归并排序求交集：" << *it << endl;
    }
    
    return 0;
}